home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graphics / map.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  10.7 KB  |  489 lines
  1. #include <LEDA/basic.h>
  2. #include <LEDA/slist.h>
  3. #include <LEDA/plane.h>
  4. #include <LEDA/window.h>
  5.  
  6. #include<math.h>
  7.  
  8. const int WORDS = 6;    // maximal size of placement vectors (in words)
  9.  
  10. const int N     = 96;   // maximal number of input points = 16 * WORDS
  11.  
  12. typedef unsigned long word;
  13.  
  14. class PLACEMENT
  15. {
  16.   word A[WORDS];
  17.  
  18.   word cache;      // cache of 16 last written entries
  19.  
  20.   public:
  21.  
  22.   PLACEMENT();
  23.  
  24.   word get_last_word() const { return cache;}
  25.  
  26.   word get_last_word(int i) const 
  27.   { return (i>0) ? (cache << ((16-i)<<1)) : 0; }
  28.   
  29.   int read(int i) const 
  30.   { return (A[i>>4] >> ((i&15)<<1)) & 3; }
  31.  
  32.   void write(int i, int pos) 
  33.   { A[i>>4] |= (pos << ((i&15)<<1));
  34.     cache <<=2;
  35.     cache |= pos;
  36.    } 
  37.  
  38.   LEDA_MEMORY(PLACEMENT)
  39.  
  40. };
  41.  
  42.  
  43. PLACEMENT::PLACEMENT()
  44. { for(int i = 0; i < WORDS; i++) A[i] = 0; }
  45.  
  46.  
  47. typedef PLACEMENT* placement;
  48.  
  49.  
  50. static window W(600,650);
  51.  
  52. static color node_color1 = blue;
  53. static color node_color2 = red;
  54. static color node_color3 = green;
  55. static color rect_color  = yellow;
  56.  
  57. void draw_rec(window& W, double x1, double y1, double x2, double y2)
  58. { if (!W.mono())
  59.       W.draw_filled_rectangle(x1,y1,x2,y2,rect_color);
  60.   W.draw_rectangle(x1,y1,x2,y2);
  61.  }
  62.  
  63.  
  64. void draw_config(window& W, const list<point>& L, PLACEMENT& P, double sig, 
  65.                                                                 int maxp = -1)
  66. {
  67.         /*--------*--------*
  68.          |        |        |
  69.          |   0    |    1   |
  70.          |        |        |
  71.          *--------p--------*
  72.          |        |        |
  73.          |   2    |    3   |
  74.          |        |        |
  75.          *--------*--------*/
  76.  
  77.   int   i=0;
  78.   point p;
  79.  
  80.   if (maxp <0) maxp = L.length();
  81.  
  82.   W.clear();
  83.  
  84.   forall(p,L)
  85.   {
  86.     double x = p.xcoord();
  87.     double y = p.ycoord();
  88.  
  89.     int  pos = P.read(i++);
  90.  
  91.     switch(pos)
  92.     { case 0 : draw_rec(W,x,y,x-sig,y+sig);
  93.                break;
  94.  
  95.       case 1 : draw_rec(W,x,y,x+sig,y+sig);
  96.                break;
  97.       
  98.       case 2 : draw_rec(W,x,y,x-sig,y-sig);
  99.                break; 
  100.       
  101.       case 3 : draw_rec(W,x,y,x+sig,y-sig);
  102.                break;
  103.     }
  104.  
  105.     if (i > maxp) break;
  106.   }
  107.  
  108.   forall(p,L) W.draw_filled_node(p,node_color1);
  109.  
  110. }
  111.  
  112.  
  113.  
  114.  
  115. int** D[N][4];   // D[N][4][N][4]
  116.                  //  
  117.                  // D[p][i][q][j] gives maximal possible sigma for square at 
  118.                  // point p in position i and square at point q in position j
  119.  
  120.  
  121. void initialize_matrix(const list<point>& p_list)
  122. {
  123.   list_item it1, it2;
  124.  
  125.   int n = p_list.length();
  126.  
  127.   int i,j,p1,p2;
  128.  
  129.   for(i=0;i < n; i++)
  130.      for(p1=0;p1 < 4; p1++)
  131.      { int** ptr = new int*[n];
  132.        D[i][p1] = ptr;
  133.        for(j=0; j<n; j++) ptr[j] = new int[4];
  134.        }
  135.  
  136.  
  137.   i = 0;
  138.   forall_items(it1,p_list)
  139.   { 
  140.     point p = p_list[it1];
  141.  
  142.     j = 0;
  143.     forall_items(it2,p_list)
  144.      { 
  145.        if (it1==it2) break;
  146.  
  147.        point q = p_list[it2];
  148.  
  149.  
  150.        int xrel  = int(p.xcoord() - q.xcoord());
  151.        int yrel  = int(p.ycoord() - q.ycoord());
  152.        int xdist = int(fabs(xrel));
  153.        int ydist = int(fabs(yrel));
  154.        int max_xy = Max(xdist,ydist);
  155.  
  156.        int d_00  = max_xy;
  157.        int d_01  = (xrel>0) ? Max(xdist/2,ydist) : MAXINT;
  158.        int d_01r = (xrel<0) ? Max(xdist/2,ydist) : MAXINT;
  159.        int d_02  = (yrel<0) ? Max(xdist,ydist/2) : MAXINT;
  160.        int d_02r = (yrel>0) ? Max(xdist,ydist/2) : MAXINT;
  161.        int d_03  = (xrel>0 && yrel<0) ? max_xy/2 : MAXINT;
  162.        int d_03r = (xrel<0 && yrel>0) ? max_xy/2 : MAXINT;
  163.        int d_12  = (xrel<0 && yrel<0) ? max_xy/2 : MAXINT;
  164.        int d_12r = (xrel>0 && yrel>0) ? max_xy/2 : MAXINT;
  165.  
  166.  
  167.        for(p1=0; p1<4;p1++)
  168.          for(p2=0; p2<4;p2++)
  169.           switch(p1 - p2)
  170.           {
  171.             case  0 : D[i][p1][j][p2] = d_00;
  172.                       break;
  173.      
  174.             case -1 : D[i][p1][j][p2] = (p1==1) ? d_12 : d_01;
  175.                       break;
  176.      
  177.             case  1 : D[i][p1][j][p2] = (p1==2) ? d_12r : d_01r;
  178.                       break;
  179.      
  180.             case -2 : D[i][p1][j][p2] = d_02;
  181.                       break;
  182.      
  183.             case  2 : D[i][p1][j][p2] = d_02r;
  184.                       break;
  185.      
  186.             case -3 : D[i][p1][j][p2] = d_03;
  187.                       break;
  188.      
  189.             case  3 : D[i][p1][j][p2] = d_03r;
  190.                       break;
  191.           }
  192.     
  193.       j++;
  194.      }
  195.  
  196.     i++;
  197.  
  198.    }
  199.  
  200. }
  201.  
  202.  
  203.  
  204.  
  205. bool find_placement(list<point>& L, int sigma, PLACEMENT& P)
  206. { 
  207.   // determines whether a placement is possible and returns it in P 
  208.   // P is unchanged if there is no placment possible 
  209.   
  210.   slist<placement> T,Tnew;
  211.  
  212.   int n = L.length();
  213.  
  214.   placement v;
  215.  
  216.   register int   p,q,k,i;
  217.   register word  buf,plw;
  218.   register int** dist_to_p;
  219.  
  220.   point a;
  221.  
  222.   float X[N];
  223.   float Y[N];
  224.  
  225.   p = 0;
  226.  
  227.   forall(a,L) 
  228.   { X[p] = a.xcoord();
  229.     Y[p] = a.ycoord();
  230.     p++;
  231.    }
  232.  
  233.   placement Pnew = new PLACEMENT;
  234.  
  235.  // we perform a sweep the strip consists of points q .. p-1 
  236.  
  237.  
  238.  // initialization for the sweep; the strip is empty; the first point to 
  239.  // enter is point 0; T consists of a single placement which is undefined 
  240.  // for all points 
  241.  
  242.  
  243.  p = 0; // next point to enter the strip
  244.  q = 0; // next point to leave the strip
  245.  
  246.  T.append(Pnew);        
  247.  
  248.  // The sweep: 
  249.  // we proceed as long as there is still a point to be processed and 
  250.  // the set T of legal placements is not empty 
  251.  
  252.  while (p < L.length() && !T.empty())
  253.  { 
  254.    // we decide whether p enters the strip or q leaves the strip 
  255.  
  256.    if (p == 0 || X[p]-X[q] < 2*sigma)
  257.      { 
  258.        // p enters the strip
  259.        // we combine the four possible placements of p 
  260.        // with all placements in T
  261.  
  262.        if (p-q > 16) error_handler(1,"too many points in strip");
  263.  
  264.        W.draw_filled_node(X[p],Y[p],node_color3);
  265.  
  266.        for(i=0; i<4; i++)
  267.        { 
  268.          dist_to_p = D[p][i];
  269.  
  270.          forall(v,T)
  271.          { // check whether v[q...p-1] can be extended by placement i for p 
  272.  
  273.            for(k = p-1, buf = v->get_last_word(); k >= q; k--, buf >>= 2)
  274.              if (dist_to_p[k][buf&3] < sigma) break;
  275.  
  276.            if (k < q)                
  277.            { // position i for p is compatible with placement vector v
  278.              Pnew = new PLACEMENT(*v);
  279.              Pnew->write(p,i);
  280.              Tnew.append(Pnew); 
  281.   
  282.              if (W.get_button() != 0) 
  283.              { color save = rect_color;
  284.                if (!W.mono()) rect_color = violet;
  285.                draw_config(W,L,*Pnew,sigma,p);
  286.                rect_color = save;
  287.                for(int i=q; i<=p; i++)
  288.                   W.draw_filled_node(X[i],Y[i],node_color2);
  289.                W.draw_filled_node(X[p],Y[p],node_color3);
  290.                W.read_mouse();
  291.                W.clear();
  292.                for(i=0; i<q; i++)
  293.                   W.draw_filled_node(X[i],Y[i],node_color1);
  294.                for(i=q; i<=p; i++)
  295.                   W.draw_filled_node(X[i],Y[i],node_color2);
  296.                for(i=p+1; i<n; i++)
  297.                   W.draw_filled_node(X[i],Y[i],node_color1);
  298.               }
  299.   
  300.             }
  301.  
  302.           }
  303.  
  304.         }
  305.  
  306.        W.draw_filled_node(X[p],Y[p],node_color2);
  307.  
  308.        p++;
  309.  
  310.        forall(v,T) delete v;
  311.  
  312.       } 
  313.     else 
  314.      { // q leaves the strip
  315.  
  316.        W.draw_filled_node(X[q],Y[q],node_color1);
  317.  
  318.        q++;
  319.  
  320.        // remove placement vectors identical in [q+1 ... p] from T
  321.  
  322.        plw = T.head()->get_last_word(p-q);
  323.  
  324.        Tnew.append(T.pop());
  325.  
  326.        forall(v,T)
  327.        { buf = v->get_last_word(p-q);
  328.          if (buf == plw)
  329.            delete v;
  330.          else 
  331.            { plw = buf;
  332.              Tnew.append(v);
  333.             }
  334.         }
  335.       }
  336.  
  337.     T.clear();
  338.     T.conc(Tnew); // clears Tnew
  339.  
  340.     W.draw_text(-80,-60,string("k = %2d   |T| = %5d   ",p-q+1,T.length()));
  341.  
  342.  } // end of sweep 
  343.  
  344.  while (q < p)
  345.  { W.draw_filled_node(X[q],Y[q],node_color1);
  346.    q++;
  347.   }
  348.  
  349.  
  350.  if (T.empty()) 
  351.      return false;
  352.  else 
  353.     { P = *(T.head());
  354.       forall(v,T) delete v;
  355.       return true;
  356.      }
  357.  
  358. } // end of find_placement 
  359.  
  360.  
  361.  
  362. main()
  363. { 
  364.   // In the first implementation we deal only with points 
  365.   // whose coordinates are integers in the range 1 .. 999;
  366.   // the algorithms consists of two steps: 
  367.   // In the first step we generate the problem and in the second step we 
  368.   // determine the optimal sigma by binary search 
  369.   // generation of the problem; we ask the user for the number of points
  370.   // then generate the appropriate number of random points 
  371.  
  372.  
  373.   W.init(-100,1100,-100);
  374.   W.set_node_width(5);
  375.   W.set_text_mode(opaque);
  376.  
  377.   if (W.mono()) 
  378.   { node_color1 = white;
  379.     node_color2 = black;
  380.    }
  381.  
  382.   int n = 50;
  383.   int input = 0;
  384.   int grid_width = 0;
  385.  
  386.   list<point> L;
  387.  
  388.   panel P;
  389.  
  390.   P.text_item("                                      ");
  391.   P.text_item("        A Plane Sweep Algorithm       ");
  392.   P.text_item("                 for a                ");
  393.   P.text_item("       Geometric Packing Problem      ");
  394.   P.text_item("                                      ");
  395.   P.text_item("                  ...                 ");
  396.   P.text_item("                  ...                 ");
  397.   P.text_item("                                      ");
  398.   P.int_item("points", n,1,80);
  399.   P.int_item("grid", grid_width, 0,40,10);
  400.  
  401.   P.button("random");
  402.   P.button("mouse");
  403.   P.button("quit");
  404.  
  405.  
  406.   for(;;)
  407.   {
  408.     int but = P.open(0,0);
  409.  
  410.     W.clear();
  411.     W.set_grid_mode(grid_width);
  412.     L.clear();
  413.  
  414.     switch(but)  {
  415.  
  416.     case 0: { init_random(n);
  417.               for(int i=0; i<n; i++) 
  418.               { double x =  random(1,999);
  419.                 double y =  random(1,999);
  420.                 L.append(point(x,y));
  421.                 W.draw_filled_node(x,y,node_color1);
  422.                }
  423.                break;
  424.              }
  425.  
  426.      case 1: { point p;
  427.                while (W >> p) 
  428.                { L.append(p);
  429.                  W.draw_filled_node(p,node_color1);
  430.                 }
  431.                break;
  432.               }
  433.  
  434.  
  435.      case 2: { exit(0);
  436.                break;
  437.               }
  438.              
  439.     }
  440.  
  441.     n = L.length();
  442.  
  443.     W.set_frame_label(string("%d points",n));
  444.  
  445.  
  446.  
  447.      // sort points  and initialize distance matrix
  448.    
  449.      L.sort();
  450.  
  451.      initialize_matrix(L);
  452.    
  453.      PLACEMENT PL;
  454.  
  455.      int low  =   1;
  456.      int high = 999;
  457.  
  458.      find_placement(L,low,PL);
  459.  
  460.      // binary search
  461.    
  462.      while (high > low+1)
  463.      { 
  464.        // Invariant:  a) PL is placement for "sigma = low"
  465.        //             b) no placement possible for "sigma = high"
  466.    
  467.        int mid = (high + low)/2;
  468.    
  469.        W.del_message();
  470.        W.message(string("%3d <= sigma < %3d      %3d ??",low, high, mid));
  471.    
  472.        if (find_placement(L,mid,PL))
  473.           { draw_config(W,L,PL,mid);
  474.             low = mid;
  475.            }
  476.         else 
  477.             high = mid;
  478.       }
  479.    
  480.      // end of the binary search 
  481.      // low is the optimal side length, PL the corresponding placement 
  482.    
  483.      W.del_message();
  484.      W.message(string("sigma = %d",low));
  485.    }
  486.                 
  487.   return 0;
  488. }
  489.